package leetcode.D400.T312;

class Solution {
    private int[] nums;

    /**
     * 动态规划
     *  dp[i][j]表示(i,j)中可以戳出的最大值，开区间表示i和j这两个气球不能戳
     *  为了连贯性，给nums首尾两端添加了两个元素，都是1
     *  状态转移：
     *      如果(i,j)中最后戳中的是k，i<k<j，那么dp[i][j] = dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j]
     */
    public int maxCoins(int[] nums) {
        int n = nums.length;
        this.nums = nums;
        int[][] dp = new int[n + 2][n + 2];
        // 初始条件
        for (int i=0; i+2<n+2; ++i)
            dp[i][i+2] = value(i) * value(i+1) * value(i+2);
        // dp循环
        int step = 3;
        while (step < n + 2) {
            for (int i=0; i+step<n+2; ++i) {
                int j = i + step, maxValue = 0;
                for (int k=i+1; k<j; ++k) {
                    int coin = dp[i][k] + dp[k][j] + value(i) * value(k) * value(j);
                    maxValue = Math.max(maxValue, coin);
                }
                dp[i][j] = maxValue;
            }
            step++;
        }
        return dp[0][n+1];
    }

    private int value(int i) {
        if (i == 0 || i == nums.length+1)
            return 1;
        return nums[i-1];
    }
}